The present invention relates generally to improved means and methods for controlling the operation of digital computers. More particularly, the present invention is directed to improved means and methods for controlling the sequencing and branching of microinstructions in a microprogrammed digital computer.
A particular architectural concept that has allowed for more flexibility in computer design and also in computer programming has been the concept of microinstructions. Initially, a microinstruction was thought of as merely a set of control bits employed within a macroinstruction format. Such control bits were employed to provide a corrective measure during the execution of a multiplying instruction or shift instruction and the like. Gradually, as the microprogramming concept enlarged, the macroinstruction specified the particular routine to be performed, such as the addition of two operands. The execution of the macroinstruction was then accomplished through a sequence of executions of microinstructions, each of which specified the particular gates to be set thereby. Since a plurality of macroinstructions could be implemented by a finite set of microinstructions, it was then apparent that these same microinstructions could be stored in a separate storage to be addressed in a particular sequence upon the execution of different macroinstructions. It was further recognized that various sequences of microinstructions could be formulated to carry out the particular operations and separately stored in any memory. Thus, a great variety of sequences of microinstructions could be created to carry out a great variety of routines, and when a given computer system was designed to perform particular routines, only those required sequences of microinstructions that would be stored could be called for to provide for execution of these particular routines.
The concept of microinstructions or microprograms, then, became one of providing sub-instructional sets which were masked or hidden from the programmer, thus, simplifying the writing of particular programs by minimizing the number of individual specific steps that had to be called for by the programmer. Furthermore, the concept of microprogramming allows the computer designer to design a more inexpensive computer system that could provide a great variety of routines to the computer user without the requirement of individual functions being implemented in hand-wired circuitry.
Microprogramming, then, can be broadly viewed as a technique for designing and implementing the control function of a digital computer system as sequences of control signals that are organized on a word basis and stored in a fixed or dynamically changeable control memory. Detailed examples of some known approaches to the design of microprogrammed digital computers can be found in the book by S.S. Husson, "Microprogramming: Principles and Practices", Prentice-Hall, Inc. (1970), the contents of which are to be regarded as incorporated herein by this reference.
As will be apparent from the referenced Husson book, a prior art microprogram control memory may typically comprise a selectively addressable control memory, usually of the read-only type, having microinstruction control words stored at selectable addressable locations thereof. Normally, microinstruction control words are accessed sequentially from the control memory. In order to provide for branching, each control word may typically include, in addition to the microinstruction bits, special next address bits and test select bits which are applied to branching logic along with system condition signals to determine the address of the next microinstruction.
Since a given microinstruction may be used in several different microroutines and with different associated next address and/or test select bits, it is usually necessary to provide sufficient storage in the control memory for storage of microinstructions at several different locations therein. In order to avoid increasing the size of the control memory as would be required by such replication, it has been proposed that a separate address memory be employed which contains sequences of microinstruction addresses for controlling the sequencing of microinstructions from a control memory in which each microinstruction is stored at only one location. (See A. Graselli, "The Design of Program-Modifiable Micro-Programmed Control Units," IRE Transactions on Electronic Computers, June 1962, pages 336-339). In such a system, branching is achieved through the utilization of tags stored along with the microinstruction addresses in the address memory which mark the beginning and the end of a microprogramming loop. When the address of the last microinstruction in a loop is accessed, the tag associated with this address will signal the system that, depending upon data and/or system status, the next address to be accessed from the address memory will be the address contained either in the next sequential word or address contained in the word which was tagged as being the beginning of the microprogramming loop.
It has also been recognized (see U.S. Pat. No. 3,794,979) that such a separate address memory as disclosed by the aforementioned Graselli article could be used to store additional control bits along with the microinstruction addresses in the address storage which permit selectively complementing and/or reversing a microinstruction accessed from the control memory before it is transmitted to a microinstruction storage data register, thereby permitting a reduction in the number of microinstructions required to be stored in the control memory.
The use of a separate address memory in the above described microprogramming approaches has made it possible to employ a control memory which has a storage capacity which is at least no greater than that required to store each different microinstruction without any repetitions, and without the need for any additionally provided next address or test select bits. However, this advantage has been achieved in the above approaches at the expense of increased complexity in the branching and conversion logic required to be provided, while also making the generation of suitable microprogramming more difficult and less flexible.